#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_V 10 // 最大顶点数

// 边结点结构（十字链表）
typedef struct ArcNode
{
    int tail;              // 弧尾顶点索引
    int head;              // 弧头顶点索引
    struct ArcNode *tlink; // 指向同一弧尾的下一条边
    struct ArcNode *hlink; // 指向同一弧头的下一条边
} ArcNode;

// 顶点结构
typedef struct
{
    char *name;        // 顶点名称
    ArcNode *firstIn;  // 以该顶点为弧头的第一条边
    ArcNode *firstOut; // 以该顶点为弧尾的第一条边
} Vertex;

// 图结构（十字链表）
typedef struct
{
    Vertex vertices[MAX_V]; // 顶点数组
    int vCount;             // 当前顶点数
} OrthogonalGraph;

// 1. 创建图
OrthogonalGraph *createGraph()
{
    OrthogonalGraph *g = (OrthogonalGraph *)malloc(sizeof(OrthogonalGraph));
    g->vCount = 0;

    // 初始化顶点数组
    for (int i = 0; i < MAX_V; i++)
    {
        g->vertices[i].name = NULL;
        g->vertices[i].firstIn = NULL;
        g->vertices[i].firstOut = NULL;
    }
    return g;
}

// 2. 添加顶点
void addVertex(OrthogonalGraph *g, const char *name)
{
    if (g->vCount >= MAX_V)
    {
        printf("Error: Graph is full\n");
        return;
    }
    g->vertices[g->vCount].name = strdup(name);
    g->vCount++;
}

// 3. 添加有向边
void addEdge(OrthogonalGraph *g, int tail, int head)
{
    if (tail < 0 || tail >= g->vCount || head < 0 || head >= g->vCount)
    {
        printf("Error: Invalid vertex index\n");
        return;
    }

    // 创建新边结点
    ArcNode *newArc = (ArcNode *)malloc(sizeof(ArcNode));
    newArc->tail = tail;
    newArc->head = head;

    // 添加到弧尾的出边链表（头插法）
    newArc->tlink = g->vertices[tail].firstOut;
    g->vertices[tail].firstOut = newArc;

    // 添加到弧头的入边链表（头插法）
    newArc->hlink = g->vertices[head].firstIn;
    g->vertices[head].firstIn = newArc;
}

// 4. 打印图
void printGraph(OrthogonalGraph *g)
{
    printf("Orthogonal List (Directed Graph):\n");

    // 打印顶点信息
    printf("Vertices:\n");
    for (int i = 0; i < g->vCount; i++)
    {
        printf("[%d] %s\n", i, g->vertices[i].name);
    }

    // 打印出边信息
    printf("\nOut Edges:\n");
    for (int i = 0; i < g->vCount; i++)
    {
        printf("%s -> ", g->vertices[i].name);
        ArcNode *outArc = g->vertices[i].firstOut;
        while (outArc)
        {
            printf("%s ", g->vertices[outArc->head].name);
            outArc = outArc->tlink;
        }
        printf("\n");
    }

    // 打印入边信息
    printf("\nIn Edges:\n");
    for (int i = 0; i < g->vCount; i++)
    {
        printf("%s <- ", g->vertices[i].name);
        ArcNode *inArc = g->vertices[i].firstIn;
        while (inArc)
        {
            printf("%s ", g->vertices[inArc->tail].name);
            inArc = inArc->hlink;
        }
        printf("\n");
    }
}

// 5. 销毁图
void destroyGraph(OrthogonalGraph *g)
{
    if (!g)
        return;

    // 释放所有边结点
    for (int i = 0; i < g->vCount; i++)
    {
        ArcNode *outArc = g->vertices[i].firstOut;
        while (outArc)
        {
            ArcNode *temp = outArc;
            outArc = outArc->tlink;
            free(temp);
        }

        free(g->vertices[i].name);
    }

    // 释放图结构
    free(g);
}

int main()
{
    // 创建图
    OrthogonalGraph *g = createGraph();

    // 添加顶点
    addVertex(g, "A");
    addVertex(g, "B");
    addVertex(g, "C");
    addVertex(g, "D");

    // 添加有向边
    addEdge(g, 0, 1); // A→B
    addEdge(g, 0, 2); // A→C
    addEdge(g, 1, 3); // B→D
    addEdge(g, 2, 3); // C→D
    addEdge(g, 3, 0); // D→A (形成环)

    // 打印图
    printGraph(g);

    // 销毁图
    destroyGraph(g);

    return 0;
}